{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Path Quality of a Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #array #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #数组 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximalPathQuality"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大化一张图中的路径价值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一张 <strong>无向</strong>&nbsp;图，图中有 <code>n</code>&nbsp;个节点，节点编号从 <code>0</code>&nbsp;到 <code>n - 1</code>&nbsp;（<strong>都包括</strong>）。同时给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>values</code>&nbsp;，其中&nbsp;<code>values[i]</code>&nbsp;是第 <code>i</code>&nbsp;个节点的 <strong>价值</strong>&nbsp;。同时给你一个下标从 <strong>0</strong>&nbsp;开始的二维整数数组&nbsp;<code>edges</code>&nbsp;，其中&nbsp;<code>edges[j] = [u<sub>j</sub>, v<sub>j</sub>, time<sub>j</sub>]</code>&nbsp;表示节点&nbsp;<code>u<sub>j</sub></code> 和&nbsp;<code>v<sub>j</sub></code>&nbsp;之间有一条需要&nbsp;<code>time<sub>j</sub></code>&nbsp;秒才能通过的无向边。最后，给你一个整数&nbsp;<code>maxTime</code>&nbsp;。</p>\n",
    "\n",
    "<p><strong>合法路径</strong>&nbsp;指的是图中任意一条从节点&nbsp;<code>0</code>&nbsp;开始，最终回到节点 <code>0</code>&nbsp;，且花费的总时间 <strong>不超过</strong>&nbsp;<code>maxTime</code> 秒的一条路径。你可以访问一个节点任意次。一条合法路径的 <b>价值</b>&nbsp;定义为路径中 <strong>不同节点</strong>&nbsp;的价值 <strong>之和</strong>&nbsp;（每个节点的价值 <strong>至多</strong>&nbsp;算入价值总和中一次）。</p>\n",
    "\n",
    "<p>请你返回一条合法路径的 <strong>最大</strong>&nbsp;价值。</p>\n",
    "\n",
    "<p><strong>注意：</strong>每个节点 <strong>至多</strong>&nbsp;有 <strong>四条</strong>&nbsp;边与之相连。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/19/ex1drawio.png\" style=\"width: 269px; height: 170px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>values = [0,32,10,43], edges = [[0,1,10],[1,2,15],[0,3,10]], maxTime = 49\n",
    "<b>输出：</b>75\n",
    "<strong>解释：</strong>\n",
    "一条可能的路径为：0 -&gt; 1 -&gt; 0 -&gt; 3 -&gt; 0 。总花费时间为 10 + 10 + 10 + 10 = 40 &lt;= 49 。\n",
    "访问过的节点为 0 ，1 和 3 ，最大路径价值为 0 + 32 + 43 = 75 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/19/ex2drawio.png\" style=\"width: 269px; height: 170px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>values = [5,10,15,20], edges = [[0,1,10],[1,2,10],[0,3,10]], maxTime = 30\n",
    "<b>输出：</b>25\n",
    "<strong>解释：</strong>\n",
    "一条可能的路径为：0 -&gt; 3 -&gt; 0 。总花费时间为 10 + 10 = 20 &lt;= 30 。\n",
    "访问过的节点为 0 和 3 ，最大路径价值为 5 + 20 = 25 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/19/ex31drawio.png\" style=\"width: 236px; height: 170px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>values = [1,2,3,4], edges = [[0,1,10],[1,2,11],[2,3,12],[1,3,13]], maxTime = 50\n",
    "<b>输出：</b>7\n",
    "<strong>解释：</strong>\n",
    "一条可能的路径为：0 -&gt; 1 -&gt; 3 -&gt; 1 -&gt; 0 。总花费时间为 10 + 13 + 13 + 10 = 46 &lt;= 50 。\n",
    "访问过的节点为 0 ，1 和 3 ，最大路径价值为 1 + 2 + 4 = 7 。</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/21/ex4drawio.png\" style=\"width: 270px; height: 71px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>values = [0,1,2], edges = [[1,2,10]], maxTime = 10\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>\n",
    "唯一一条路径为 0 。总花费时间为 0 。\n",
    "唯一访问过的节点为 0 ，最大路径价值为 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == values.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= values[i] &lt;= 10<sup>8</sup></code></li>\n",
    "\t<li><code>0 &lt;= edges.length &lt;= 2000</code></li>\n",
    "\t<li><code>edges[j].length == 3 </code></li>\n",
    "\t<li><code>0 &lt;= u<sub>j </sub>&lt; v<sub>j</sub> &lt;= n - 1</code></li>\n",
    "\t<li><code>10 &lt;= time<sub>j</sub>, maxTime &lt;= 100</code></li>\n",
    "\t<li><code>[u<sub>j</sub>, v<sub>j</sub>]</code>&nbsp;所有节点对 <strong>互不相同</strong>&nbsp;。</li>\n",
    "\t<li>每个节点 <strong>至多有四条&nbsp;</strong>边。</li>\n",
    "\t<li>图可能不连通。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-path-quality-of-a-graph](https://leetcode.cn/problems/maximum-path-quality-of-a-graph/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-path-quality-of-a-graph](https://leetcode.cn/problems/maximum-path-quality-of-a-graph/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,32,10,43]\\n[[0,1,10],[1,2,15],[0,3,10]]\\n49', '[5,10,15,20]\\n[[0,1,10],[1,2,10],[0,3,10]]\\n30', '[1,2,3,4]\\n[[0,1,10],[1,2,11],[2,3,12],[1,3,13]]\\n50']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.mark = []\n",
    "        self.adj = []\n",
    "        self.value = []\n",
    "        self.ret = 0\n",
    "\n",
    "    def dfs(self, pos, sum, time):\n",
    "        if self.mark[pos] == 0:\n",
    "            sum += self.value[pos]\n",
    "        if sum > self.ret and pos == 0:\n",
    "            self.ret = sum\n",
    "        self.mark[pos] += 1\n",
    "        for i in range(len(self.adj[pos])):\n",
    "            if self.adj[pos][i][1] <= time:\n",
    "                self.dfs(self.adj[pos][i][0], sum, time - self.adj[pos][i][1])\n",
    "        self.mark[pos] -= 1\n",
    "\n",
    "    def maximalPathQuality(self, values, edges, maxTime):\n",
    "        n = len(values)\n",
    "        self.value = values\n",
    "        adj_ = [[] for _ in range(n)]\n",
    "        for i in range(len(edges)):\n",
    "            adj_[edges[i][0]].append([edges[i][1], edges[i][2]])\n",
    "            adj_[edges[i][1]].append([edges[i][0], edges[i][2]])\n",
    "        self.adj = adj_\n",
    "        mark_ = [0] * n\n",
    "        self.mark = mark_\n",
    "        self.dfs(0, 0, maxTime)\n",
    "        return self.ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "        n = len(values)\n",
    "        self.value = values\n",
    "        adj_ = [[] for _ in range(n)]\n",
    "        for i in range(len(edges)):\n",
    "            adj_[edges[i][0]].append([edges[i][1], edges[i][2]])\n",
    "            adj_[edges[i][1]].append([edges[i][0], edges[i][2]])\n",
    "        self.adj = adj_\n",
    "        mark_ = [0] * n\n",
    "        self.mark = mark_\n",
    "        self.dfs(0, 0, maxTime)\n",
    "        return self.ret\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.mark = []\n",
    "        self.adj = []\n",
    "        self.value = []\n",
    "        self.ret = 0\n",
    "\n",
    "    def dfs(self, pos, sum, time):\n",
    "        if self.mark[pos] == 0:\n",
    "            sum += self.value[pos]\n",
    "        if sum > self.ret and pos == 0:\n",
    "            self.ret = sum\n",
    "        self.mark[pos] += 1\n",
    "        for i in range(len(self.adj[pos])):\n",
    "            if self.adj[pos][i][1] <= time:\n",
    "                self.dfs(self.adj[pos][i][0], sum, time - self.adj[pos][i][1])\n",
    "        self.mark[pos] -= 1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "        def backtrace(x: int, past_time: int, cur_money: int) -> None:\n",
    "            nonlocal res\n",
    "            if x == 0:\n",
    "                res = max(res, cur_money)\n",
    "            for y, cost in adjvex[x]:\n",
    "                if past_time + cost <= maxTime:\n",
    "                    if visited[y] == False:\n",
    "                        visited[y] = True\n",
    "                        backtrace(y, past_time + cost, cur_money + values[y])\n",
    "                        visited[y] = False\n",
    "                    else:\n",
    "                        backtrace(y, past_time + cost, cur_money)\n",
    "\n",
    "        N = len(values)\n",
    "        adjvex = collections.defaultdict(list)\n",
    "        for x, y, time in edges:\n",
    "            adjvex[x].append((y, time))\n",
    "            adjvex[y].append((x, time))\n",
    "            \n",
    "        res = 0    \n",
    "        visited = [False for _ in range(N)]\n",
    "        visited[0] = True\n",
    "        backtrace(0, 0, values[0])\n",
    "                        \n",
    "        return max(values[0], res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "        tp,rr={},0\n",
    "        for e in edges:\n",
    "            if e[0] in tp:tp[e[0]]+=[(e[1],e[2])]\n",
    "            else:tp[e[0]]=[(e[1],e[2])]\n",
    "            if e[1] in tp:tp[e[1]]+=[(e[0],e[2])]\n",
    "            else:tp[e[1]]=[(e[0],e[2])]\n",
    "        if 0 not in tp:return values[0]\n",
    "        dq,mi,rr=[(0,values[0],[0])],[0]*len(values),0\n",
    "        while dq:\n",
    "            t,v,p=heapq.heappop(dq)\n",
    "            if p[-1]==0:rr=max(rr,v)\n",
    "            if mi[p[-1]]>v:continue\n",
    "            mi[p[-1]]=v\n",
    "            for pp,tt in tp[p[-1]]:\n",
    "                if t+tt>maxTime:continue\n",
    "                if pp in p:heapq.heappush(dq,(t+tt,v,p+[pp]))\n",
    "                else:heapq.heappush(dq,(t+tt,v+values[pp],p+[pp]))\n",
    "        return rr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "        m = defaultdict(list)\n",
    "        for f, t, time in edges:\n",
    "            m[f].append((t, time))\n",
    "            m[t].append((f, time))\n",
    "        s = defaultdict(int)\n",
    "        maxl = values[0]\n",
    "        def dfs(p, v, t):\n",
    "            if p == 0:\n",
    "                nonlocal maxl\n",
    "                maxl = max(maxl, v)\n",
    "            for np, time in m[p]:\n",
    "                if t + time <= maxTime:\n",
    "                    nv = v\n",
    "                    if s[np] == 0:\n",
    "                        nv =  v + values[np]\n",
    "                    s[np] += 1\n",
    "                    dfs(np, nv, t + time)\n",
    "                    s[np] -= 1\n",
    "        s[0] = 1\n",
    "        dfs(0, values[0], 0)\n",
    "        return maxl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for x, y, w in edges:\n",
    "            g[x].append((y, w))\n",
    "            g[y].append((x, w))\n",
    "        vis = set([0])\n",
    "        ans = 0\n",
    "        def dfs(u, val, t):\n",
    "            if u == 0:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, val)\n",
    "            for nxt, w in g[u]:\n",
    "                if t + w <= maxTime:\n",
    "                    if nxt not in vis:\n",
    "                        vis.add(nxt)\n",
    "                        dfs(nxt, val+values[nxt], t+w)\n",
    "                        vis.discard(nxt)\n",
    "                    else:\n",
    "                        dfs(nxt, val, t+w)\n",
    "        dfs(0, values[0], 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "\n",
    "        for x,y,v in edges:\n",
    "             g[x].append((y,v))\n",
    "             g[y].append((x,v))\n",
    "        visited = {0}\n",
    "        max_valus = 0\n",
    "        def dfs(node_s,costTime,value):\n",
    "            if node_s==0:\n",
    "                nonlocal max_valus\n",
    "                max_valus = max(max_valus,value)\n",
    "            for v, dist in g[node_s]:\n",
    "                if dist+costTime <= maxTime:\n",
    "                    if v not in visited:\n",
    "                        visited.add(v)\n",
    "                        dfs(v, costTime + dist, value + values[v])\n",
    "                        visited.discard(v)\n",
    "                    else:\n",
    "                        dfs(v, costTime + dist, value)\n",
    "        dfs(0,0,values[0])\n",
    "        return max_valus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "\n",
    "        def backtrace(x: int, past_time: int, cur_money: int) -> None:\n",
    "\n",
    "            nonlocal res\n",
    "\n",
    "            if x == 0:\n",
    "\n",
    "                res = max(res, cur_money)\n",
    "\n",
    "            for y, cost in adjvex[x]:\n",
    "\n",
    "                if past_time + cost <= maxTime:\n",
    "\n",
    "                    if visited[y] == False:\n",
    "\n",
    "                        visited[y] = True\n",
    "\n",
    "                        backtrace(y, past_time + cost, cur_money + values[y])\n",
    "\n",
    "                        visited[y] = False\n",
    "\n",
    "                    else:\n",
    "\n",
    "                        backtrace(y, past_time + cost, cur_money)\n",
    "\n",
    "\n",
    "\n",
    "        N = len(values)\n",
    "\n",
    "        adjvex = collections.defaultdict(list)\n",
    "\n",
    "        for x, y, time in edges:\n",
    "\n",
    "            adjvex[x].append((y, time))\n",
    "\n",
    "            adjvex[y].append((x, time))\n",
    "\n",
    "            \n",
    "\n",
    "        res = 0    \n",
    "\n",
    "        visited = [False for _ in range(N)]\n",
    "\n",
    "        visited[0] = True\n",
    "\n",
    "        backtrace(0, 0, values[0])\n",
    "\n",
    "                        \n",
    "\n",
    "        return max(values[0], res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "        n = len(values)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for a, b, t in edges:\n",
    "            graph[a].append((b, t))\n",
    "            graph[b].append((a, t))\n",
    "        ans = 0\n",
    "        def dfs(node, stime, val):\n",
    "            nonlocal ans\n",
    "            val += values[node]\n",
    "            if stime > maxTime: return\n",
    "            if node == 0: ans = max(ans, val)\n",
    "            for nx, nt in graph[node]:\n",
    "                x = values[node]\n",
    "                values[node] = 0\n",
    "                dfs(nx, stime + nt, val)\n",
    "                values[node] = x\n",
    "\n",
    "        dfs(0, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for x, y, z in edges:\n",
    "            g[x].append((y, z))\n",
    "            g[y].append((x, z))\n",
    "        \n",
    "        visited = {0}\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(u, time, value):\n",
    "            if u == 0:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, value)\n",
    "            for v, dist in g[u]:\n",
    "                if time + dist <= maxTime:\n",
    "                    if v not in visited:\n",
    "                        visited.add(v)\n",
    "                        dfs(v, time+dist, value+values[v])\n",
    "                        visited.discard(v)\n",
    "                    else:\n",
    "                        dfs(v, time+dist, value)\n",
    "        \n",
    "        dfs(0, 0, values[0])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "        n=len(values)\n",
    "        ch=[[] for _ in range(n)]\n",
    "        tr=set()\n",
    "        res=0\n",
    "        def dfs(i,t,v):\n",
    "            f=i not in tr\n",
    "            if f:\n",
    "                tr.add(i)\n",
    "                v+=values[i]\n",
    "            if i==0:\n",
    "                nonlocal res\n",
    "                res=max(res,v)\n",
    "            for j,w in ch[i]:\n",
    "                if t+w<=maxTime:\n",
    "                    dfs(j,t+w,v)\n",
    "            if f:\n",
    "                tr.remove(i)\n",
    "                v-=values[i]\n",
    "        for u,v,t in edges:\n",
    "            ch[u].append((v,t))\n",
    "            ch[v].append((u,t))\n",
    "        dfs(0,0,0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for x, y, z in edges:\n",
    "            g[x].append((y, z))\n",
    "            g[y].append((x, z))\n",
    "        \n",
    "        visited = {0}\n",
    "        ans = 0\n",
    "        \n",
    "        def dfs(u: int, time: int, value: int) -> None:\n",
    "            if u == 0:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, value)\n",
    "            for v, dist in g[u]:\n",
    "                if time + dist <= maxTime:\n",
    "                    if v not in visited:\n",
    "                        visited.add(v)\n",
    "                        dfs(v, time + dist, value + values[v])\n",
    "                        visited.discard(v)\n",
    "                    else:\n",
    "                        dfs(v, time + dist, value)\n",
    "        \n",
    "        dfs(0, 0, values[0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "        ljt = defaultdict(list)\n",
    "        for x0, x1, x2 in edges:\n",
    "            ljt[x0].append((x1, x2))\n",
    "            ljt[x1].append((x0, x2))\n",
    "\n",
    "        used = {0}\n",
    "        maxv = 0\n",
    "\n",
    "        def dfs(edge, time, value):\n",
    "            if edge == 0:\n",
    "                nonlocal maxv\n",
    "                maxv = max(value, maxv)\n",
    "\n",
    "            for idx, tt in ljt[edge]:\n",
    "                if time + tt <= maxTime:\n",
    "                    if idx not in used:\n",
    "                        used.add(idx)\n",
    "                        dfs(idx, time + tt, value + values[idx])\n",
    "                        used.remove(idx)\n",
    "                    else:\n",
    "                        dfs(idx, time + tt, value)\n",
    "\n",
    "        dfs(0, 0, values[0])\n",
    "        return maxv"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "        # 1. O(E) build adjacency list of undirected graph\n",
    "        n = len(values)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, w in edges:\n",
    "            g[u].append((v, w))\n",
    "            g[v].append((u, w))\n",
    "        \n",
    "        # 2. O(V) DFS\n",
    "        def dfs(u: int, time: int, value: int, path: List[int]) -> None:\n",
    "            nonlocal ans\n",
    "            path.append(u)\n",
    "            if u == start:\n",
    "                ans = max(ans, value)\n",
    "            for v, w in g[u]:\n",
    "                if time + w <= maxTime:\n",
    "                    if not visited[v]:\n",
    "                        visited[v] = True \n",
    "                        dfs(v, time + w, value + values[v], path)\n",
    "                        visited[v] = False \n",
    "                    else:\n",
    "                        dfs(v, time + w, value, path)\n",
    "            path.pop()\n",
    "        \n",
    "\n",
    "        ans = 0\n",
    "        path = []\n",
    "        start = 0\n",
    "        visited = [False] * n \n",
    "        visited[start] = True \n",
    "        dfs(start, 0, values[start], path)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for u, v, t in edges:\n",
    "            g[u].append((v, t))\n",
    "            g[v].append((u, t))\n",
    "        \n",
    "        ans = 0\n",
    "        vis = {0}\n",
    "        \n",
    "        def dfs(x, time, val):\n",
    "            if x == 0:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, val)\n",
    "            for y, t in g[x]:\n",
    "                if t + time > maxTime: continue\n",
    "                if y not in vis:\n",
    "                    vis.add(y)\n",
    "                    dfs(y, t + time, val + values[y])\n",
    "                    vis.discard(y)\n",
    "                else:\n",
    "                    dfs(y, t+ time, val)\n",
    "        \n",
    "        dfs(0, 0, values[0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Dijkstra:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def get_dijkstra_result(dct: List[List[int]], src: int) -> List[float]:\n",
    "        # 模板: Dijkstra求最短路，变成负数求可以求最长路（还是正权值）\n",
    "        n = len(dct)\n",
    "        dis = [inf] * n\n",
    "        stack = [[0, src]]\n",
    "        dis[src] = 0\n",
    "\n",
    "        while stack:\n",
    "            d, i = heapq.heappop(stack)\n",
    "            if dis[i] < d:\n",
    "                continue\n",
    "            for j, w in dct[i]:\n",
    "                dj = w + d\n",
    "                if dj < dis[j]:\n",
    "                    dis[j] = dj\n",
    "                    heapq.heappush(stack, [dj, j])\n",
    "        return dis\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "        n = len(values)\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j, t in edges:\n",
    "            dct[i].append([j, t])\n",
    "            dct[j].append([i, t])\n",
    "        dis = Dijkstra().get_dijkstra_result(dct, 0)\n",
    "\n",
    "        stack = [[0, 0, {0}]]\n",
    "        ans = 0\n",
    "        visit = {tuple(sorted({0}) + [0]): 0}\n",
    "        while stack:\n",
    "            t, x, nodes = heappop(stack)\n",
    "            if x == 0:\n",
    "                cur = sum(values[j] for j in nodes)\n",
    "                if cur > ans:\n",
    "                    ans = cur\n",
    "            for y, w in dct[x]:\n",
    "                if t + w + dis[y] <= maxTime:\n",
    "                    state = tuple(sorted(nodes.union({y})) + [y])\n",
    "                    if visit.get(state, inf) > t + w:\n",
    "                        visit[state] = t + w\n",
    "                        heappush(stack, [t+w, y, nodes.union({y})])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "        n = len(values)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y,z in edges:\n",
    "            g[x].append((y,z))\n",
    "            g[y].append((x,z))\n",
    "        ans = values[0]\n",
    "\n",
    "        def dfs(i,curTime,v):\n",
    "            nonlocal ans\n",
    "            if curTime > maxTime:\n",
    "                return \n",
    "            if curTime <= maxTime and i == 0:\n",
    "                # print(i,curTime,v)\n",
    "                ans = max(ans,v)\n",
    "            for j,t in g[i]:\n",
    "                nv = v + values[j]\n",
    "                vv = values[j]\n",
    "                values[j] = 0\n",
    "                \n",
    "                dfs(j,curTime+t,nv)\n",
    "                values[j] = vv\n",
    "                \n",
    "        \n",
    "        dfs(0,0,0)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "        n = len(values)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y, t in edges:\n",
    "            g[x].append((y, t))\n",
    "            g[y].append((x, t))\n",
    "        ans = values[0]\n",
    "        def dfs(x, cur_cost, cur_val, has):\n",
    "            if x == 0:\n",
    "                nonlocal ans\n",
    "                ans = cur_val if cur_val > ans else ans\n",
    "            for y, t in g[x]:\n",
    "                if cur_cost + t <= maxTime:\n",
    "                    if y not in has:\n",
    "                        has.add(y)\n",
    "                        dfs(y, cur_cost + t, cur_val + values[y], has)\n",
    "                        has.remove(y)\n",
    "                    else:\n",
    "                        dfs(y, cur_cost + t, cur_val, has)\n",
    "        dfs(0, 0, values[0], set([0]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\r\n",
    "        visited = [False] * len(values)\r\n",
    "        conn: list[list[tuple[int, int]]] = [[] for _ in range(len(values))]\r\n",
    "        for u, v, t in edges:\r\n",
    "            conn[u].append((v, t))\r\n",
    "            conn[v].append((u, t))\r\n",
    "        \r\n",
    "        res = 0\r\n",
    "        \r\n",
    "        def dfs(node: int, tm: int, val: int) -> None:\r\n",
    "            nonlocal res\r\n",
    "            if tm > maxTime: return\r\n",
    "            if node == 0: res = max(res, val)\r\n",
    "            \r\n",
    "            for nxt, t in conn[node]:\r\n",
    "                if not visited[nxt]:\r\n",
    "                    visited[nxt] = True\r\n",
    "                    dfs(nxt, tm + t, val + values[nxt])\r\n",
    "                    visited[nxt] = False\r\n",
    "                else:\r\n",
    "                    dfs(nxt, tm + t, val)\r\n",
    "        \r\n",
    "        visited[0] = True\r\n",
    "        dfs(0, 0, values[0])\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "        n = len(values)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, w in edges:\n",
    "            g[u].append((v, w))\n",
    "            g[v].append((u, w))\n",
    "        \n",
    "        \n",
    "        def dfs(u: int, time: int, value: int) -> None:\n",
    "            nonlocal ans\n",
    "            if u == 0:\n",
    "                ans = max(ans, value)\n",
    "            for v, w in g[u]:\n",
    "                if time + w <= maxTime:\n",
    "                    if not visited[v]:\n",
    "                        visited[v] = True \n",
    "                        dfs(v, time + w, value + values[v])\n",
    "                        visited[v] = False \n",
    "                    else:\n",
    "                        dfs(v, time + w, value)\n",
    "        \n",
    "\n",
    "        ans = 0\n",
    "        start = 0\n",
    "        visited = [False] * n \n",
    "        visited[start] = True \n",
    "        dfs(start, 0, values[start])\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "        n = len(values)\n",
    "        graph = defaultdict(list)\n",
    "        for u,v,t in edges:\n",
    "            graph[u].append((v,t))\n",
    "            graph[v].append((u,t))\n",
    "        \n",
    "        self.res = 0\n",
    "\n",
    "        def dfs(x, temp_sum, rec, remain_t):\n",
    "            if remain_t < 0:\n",
    "                return\n",
    "            if x == 0:\n",
    "                self.res = max(self.res, temp_sum)\n",
    "                \n",
    "            for nextN,nextT in graph[x]:\n",
    "                if rec[nextN]:\n",
    "                    dfs(nextN, temp_sum, rec, remain_t-nextT)\n",
    "                else:\n",
    "                    rec[nextN] = True\n",
    "                    dfs(nextN, temp_sum+values[nextN], rec, remain_t-nextT)\n",
    "                    rec[nextN] = False\n",
    "\n",
    "        mrec = [False]*n\n",
    "        mrec[0] = True\n",
    "        dfs(0, values[0], mrec, maxTime)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "        # 1. O(E) build adjacency list of undirected graph\n",
    "        n = len(values)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, w in edges:\n",
    "            g[u].append((v, w))\n",
    "            g[v].append((u, w))\n",
    "        \n",
    "        # 2. O(V) DFS\n",
    "        def dfs(u: int, time: int, value: int, path: List[int]) -> None:\n",
    "            nonlocal ans\n",
    "            if time > maxTime:\n",
    "                return \n",
    "            path.append(u)\n",
    "            if visited[u] == 0:\n",
    "                value += values[u] \n",
    "            visited[u] += 1\n",
    "            if u == start:\n",
    "                ans = max(ans, value)\n",
    "            for v, w in g[u]:\n",
    "                dfs(v, time + w, value, path)\n",
    "            \n",
    "            visited[u] -= 1 \n",
    "            path.pop()\n",
    "        \n",
    "\n",
    "        ans = 0\n",
    "        path = []\n",
    "        start = 0\n",
    "        visited = [0] * n  \n",
    "        dfs(start, 0, 0, path)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "        # 1 <= n <= 1000\n",
    "        # 看着像是树状DP\n",
    "        # 注意：每个节点 至多 有 四条 边与之相连。绝对是解决问题的关键信息 10 <= timej, maxTime <= 100 ；；最多也就10条边，直接暴力就行\n",
    "        g = defaultdict(list)\n",
    "        time = defaultdict(list)\n",
    "        for u, v, t in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "            time[(u, v)] = t\n",
    "            time[(v, u)] = t\n",
    "        \n",
    "        def dfs(node, maxTime, vis, dist):\n",
    "            if vis >> node & 1 == 0:\n",
    "                dist += values[node]\n",
    "                vis |= 1 << node\n",
    "            if node == 0:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, dist)\n",
    "            for s in g[node]:\n",
    "                if time[(node, s)] <= maxTime:\n",
    "                    dfs(s, maxTime-time[(node, s)], vis, dist)\n",
    "        \n",
    "        ans = 0\n",
    "        dfs(0, maxTime, 0, 0)\n",
    "        return ans\n",
    "            \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "        adj = [[] for i in range(len(values))]\n",
    "        for i in range(len(edges)):\n",
    "            adj[edges[i][0]].append([edges[i][1],edges[i][2]])\n",
    "            adj[edges[i][1]].append([edges[i][0],edges[i][2]])\n",
    "\n",
    "        visit = [0 for i in range(len(values))]\n",
    "        visit[0] = 1\n",
    "        res = 0\n",
    "        def dfs(x,t,val_sum):\n",
    "            nonlocal res\n",
    "            if x == 0:\n",
    "                res = max(res,val_sum)\n",
    "            for i in range(len(adj[x])):\n",
    "                if t + adj[x][i][1] <= maxTime:\n",
    "                    if visit[adj[x][i][0]] == 0:\n",
    "                        visit[adj[x][i][0]] = 1\n",
    "                        dfs(adj[x][i][0],t+adj[x][i][1],val_sum+values[adj[x][i][0]])\n",
    "                        visit[adj[x][i][0]] = 0\n",
    "                    else:\n",
    "                        dfs(adj[x][i][0],t+adj[x][i][1],val_sum)\n",
    "        dfs(0,0,values[0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "\n",
    "        graph = defaultdict(lambda : defaultdict(int))\n",
    "        for u , v , weight in edges:\n",
    "            graph[u][v] = weight\n",
    "            graph[v][u] = weight\n",
    "\n",
    "        visited = []\n",
    "\n",
    "        def dfs(node,t):\n",
    "            nonlocal ans\n",
    "            if t > maxTime:return\n",
    "            if node == 0:\n",
    "                ans = max(ans,sum([values[i] for i in set(visited)]))\n",
    "            for k , v in graph[node].items():\n",
    "                visited.append(k)\n",
    "                dfs(k,t+v)\n",
    "                visited.pop()\n",
    "        ans = values[0]\n",
    "        dfs(0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, v: List[int], e: List[List[int]], maxTime: int) -> int:\n",
    "        g = [[] for j in range(len(v))] \n",
    "        n = len(v)\n",
    "        for x, y, val in e:\n",
    "            g[x].append([y, val]) \n",
    "            g[y].append([x, val]) \n",
    "        vis = {0}\n",
    "        self.ans = -1\n",
    "        def dfs(x, res, pre):\n",
    "            if res<0:\n",
    "                return \n",
    "            if x==0:\n",
    "                self.ans = max(self.ans, pre)\n",
    "            for y, val in g[x]:\n",
    "                if y in vis:\n",
    "                    dfs(y, res-val, pre) \n",
    "                else:\n",
    "                    vis.add(y)\n",
    "                    dfs(y, res-val, pre+v[y])\n",
    "                    vis.remove(y)\n",
    "                        \n",
    "        dfs(0, maxTime, v[0])\n",
    "        return self.ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n",
    "        tp,rr={},0\n",
    "        for e in edges:\n",
    "            if e[0] in tp:tp[e[0]]+=[(e[1],e[2])]\n",
    "            else:tp[e[0]]=[(e[1],e[2])]\n",
    "            if e[1] in tp:tp[e[1]]+=[(e[0],e[2])]\n",
    "            else:tp[e[1]]=[(e[0],e[2])]\n",
    "        if 0 not in tp:return values[0]\n",
    "        def dfs(p,t,v):\n",
    "            nonlocal rr\n",
    "            if t>maxTime:return\n",
    "            if p[-1]==0:\n",
    "                rr=max(rr,v)\n",
    "            for pp,tt in tp[p[-1]]:\n",
    "                if pp in p:dfs(p+[pp],t+tt,v)\n",
    "                else:dfs(p+[pp],t+tt,v+values[pp])\n",
    "        dfs([0],0,values[0])\n",
    "        return rr"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
